from sudoku import SudokuBoard
from random import choice
from collections import deque
import math

class SudokuSolver:
	'''
	Class for the sudoku solver.
	'''

	def __init__(self):
		pass
			
	def solve(self, filename, use_FC=True, use_MRV=True, use_MCV=True, use_AC3=True):
		board = self.init_board(filename)
#		print board.const
#		print board.allowed_values
		print 'Solving %s: FC-%s MRV-%s MCV-%s AC3-%s' % (filename, use_FC, use_MRV, use_MCV, use_AC3)
		print 'Starting state'
		board.__repr__()
		solution, total_checks = self.sudoku_backtrack(board, 0, use_FC, use_MRV, use_MCV, use_AC3)
		if solution == True:
			print 'Solution after %d checks' % total_checks
			board.__repr__()
		else:
			print 'No solution found'
	
	def init_board(self, filename):
		'''
		This function will parse a sudoku text file (like those posted on the website)
		into a size, and a 2d array [row,col] which holds the value of each cell.
		array elements with a value of 0 are considered to be empty
		'''
		f = open(filename, 'r')
		BoardSize = int(f.readline())
		NumVals = int(f.readline())
	
		#initialize a blank board
		board = [ [ 0 for i in range(BoardSize) ] for j in range(BoardSize) ]
	
		#populate the board with initial values
		for i in range(NumVals):
			row, col, val = map(int, f.readline().split('\t'))
			board[row - 1][col - 1] = val
		
		return SudokuBoard(len(board), board)

	def sudoku_backtrack(self, sudoku, n_checks, use_FC, use_MRV, use_MCV, use_AC3):
		'''
		Function for backtracking
		'''
		current_checks = n_checks
		if sudoku.is_complete():
			return (True, current_checks)
		else:
			# Select an unassigned variable
			row, col = self.select_variable(sudoku, use_MRV, use_MCV)
			# Select a value from the domain
			values = self.select_values(sudoku, row, col, use_FC, use_AC3)
			for value in values:
				# If consistent with constraints, assign value to variable
				check_result = self.check_constraints(sudoku, row, col, value)
				current_checks += 1
				if check_result == True:
					# Create a new board with the constraints already updated
					new_board = sudoku.set_value(row, col, value)
					
					if use_FC == True:
						if self.forward_check(new_board, row, col, value) == False:
							sudoku.board[row][col] = 0
							continue
						
					if use_AC3 == True:
						if self.arc_consistency(new_board) == False:
							sudoku.board[row][col] = 0
							continue
					
					child_result, current_checks = self.sudoku_backtrack(new_board, current_checks, use_FC, use_MRV, use_MCV, use_AC3)
					
					if child_result == True:
						# Update the constraints for the old board
						sudoku.update_const(row, col, value)
						return (True, current_checks)
				# Remove assignment
				sudoku.board[row][col] = 0
		return (False, current_checks)
	
	def check_constraints(self, sudoku, row, col, value):
		if value in sudoku.allowed_values[row][col]:
			return True
		else:
			return False
	
	def forward_check(self, sudoku, row, col, val):
		'''
		Function that implements forward checking. Consider revision.
		'''
		subsquare = int(math.sqrt(sudoku.size))
		
		for i in range(sudoku.size):
			# checks row for val
			if sudoku.allowed_values[row][i] == [] and i != col:
				return False
			# checks col for val	
			if sudoku.allowed_values[i][col] == [] and i != row:
				return False
			
			SquareRow = row // subsquare
			SquareCol = col // subsquare
			# checks square of [row][col] for val
			for i in range(subsquare):
				for j in range(subsquare):
					if((sudoku.allowed_values[SquareRow * subsquare + i][SquareCol * subsquare + j] == [])
					and (SquareRow * subsquare + i != row) and (SquareCol * subsquare + j != col)):
						return False
					
		return True
	
	def revise(self, sudoku, var):
		'''
		Function that revises the domain of var using its binary constraints
		'''
		
		revised = False
	
		for x in sudoku.allowed_values[var[0][0]][var[0][1]]:
			y = sudoku.allowed_values[var[1][0]][var[1][1]]

			# if Y has been assigned a value y we removed it from the domain of var
			if len(y) == 1 and y[0] == x:
				sudoku.allowed_values[var[0][0]][var[0][1]].remove(x)
				revised = True
		return revised
		
	def arc_consistency(self, sudoku):
		'''
		Implementation of the arc-consistency heuristics
		'''
		
		# creates a queue with all binary constraints
		arcs_qu = deque(sudoku.arcs)
		
		while len(arcs_qu) != 0:
			var = arcs_qu.popleft()

			if self.revise(sudoku, var):
				# if var has no values left then the assignment is inconsistent
				if len(sudoku.allowed_values[var[0][0]][var[0][1]]) == 0:
					return False
					
				# add each binary constraint that var is first-in to the queue
				for row in range(sudoku.size):
					for col in range(sudoku.size):
						if (var[0], (row, col)) in sudoku.arcs:
							arcs_qu.append(((row, col), var[0]))
		return True

	def select_variable(self, sudoku, use_MRV=True, use_MCV=True):
		'''
		Function for variable selection. Implements the minimum remaining value and the most constraining variable heuristics.
		'''
		
		if use_MRV == True:
			# Use minimum remaining value heuristic
			# selects a variable for assignment that has the minimum legal values
			size = sudoku.size
			vars_min_vals = []
			min_vals = size
		
			# check each cell for the variable with the least legal values
			for row in range(size):
				for col in range(size):
					if sudoku.board[row][col] == 0:
						curr_vals = len(sudoku.allowed_values[row][col])
						
						if (curr_vals == min_vals):
							vars_min_vals.append((row, col))
						if (curr_vals < min_vals):
							vars_min_vals = [(row, col)]
							min_vals = curr_vals
							
			if use_MCV == True:
				# Use most constraining variable heuristic
				vars_most_const = []
				most_const = 0
				for var_row, var_col in vars_min_vals:
					curr_const = sudoku.const[var_row][var_col]
					if curr_const == most_const:
						vars_most_const.append((var_row, var_col))
					if curr_const > most_const:
						vars_most_const = [(var_row, var_col)]
						most_const = curr_const
				
				return choice(vars_most_const)
					
			else:
				# Do not use MCV
				# Returns a random variable out of those with the mrv
				return choice(vars_min_vals)
		else:
			# Do not use MRV
			# Select the first variable that is not assigned
			for row in range(sudoku.size):
				for col in range(sudoku.size):
					if sudoku.board[row][col] == 0:
						return row, col
	
	def select_values(self, sudoku, row, col, use_FC=True, use_AC3=True):
		'''
		Function for value selection. Implements forward checking.
		'''
		
		if use_FC == True or use_AC3 == True:
			return sudoku.allowed_values[row][col]
		else:
			return range(1, sudoku.size + 1)
